package org.hot100.h020;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

/**
 * @Author: wjy
 * @Date: 2021/12/10 9:30
 */
public class Solution {

    public static void main(String[] args) {

        String str = "()[]";

        Solution solution = new Solution();
        System.out.println(solution.isValid3(str));

    }

    Map<Character, Character> map = new HashMap<Character, Character>(){{
        put('{', '}');
        put('(', ')');
        put('[', ']');
    }};

    public boolean isValid(String s) {
        if (s.length() == 0 || !map.containsKey(s.charAt(0))) {
            return false;
        }

        LinkedList<Character> linkedList = new LinkedList<Character>(){{add('?');}};

        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                linkedList.add(map.get(c));
            } else if (linkedList.removeLast() != c) {
                return false;
            }
        }

        return linkedList.size() == 1 ? true : false;
    }

    public boolean isValid2(String s) {
        if (s.length() == 0) {
            return false;
        }

        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.size() == 0 || stack.pop() != c) {
                return false;
            }
        }

        return stack.isEmpty();
    }

    public boolean isValid3(String s) {
        Stack<Character> stack = new Stack<>();

        for (Character c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
        return stack.isEmpty();
    }

}
